\section{离散傅立叶变换}

\subsection{DFT对连续时间信号频谱分析}
采样间隔 $T_{\rm s}$，采样点数 $N$，采样时长 $T_{\rm p}$\\
数字频域采样间隔 $2\pi/N$，模拟频域采样间隔 $\Delta\omega = \omega_{\rm s}/N$
$$
\Delta\omega = \frac{\omega_{\rm s}}{N} = \frac{2\pi}{T_{\rm s}N} = \frac{2\pi}{T_{\rm p}}
$$

\subsubsection{频谱分析中的问题}

\paragraph{混叠效应}
对无限频宽的信号采样造成频谱混叠
\begin{enum}
    \item 预滤波
    \item 增大采样频率
\end{enum}

\paragraph{栅栏效应}
DFT的时域延拓是对DTFT频谱的采样\\
从理论来说，只要指导DFT点数 $N$ 就可将周期延拓后的信号恢复为原信号，频谱可复原\\
对肉眼来说，给出的DFT频谱只有离散点不利于人类直接了解原信号频域\\
只要离散点足够密，就容易利用DFT频谱直接猜测原信号频谱\\
增大离散点密度的最简单方法是对序列尾部补0，增大DFT点数

增加采样频率 $f_{\rm s}$ 可改变模拟域频谱的观察范围，但不能改善模拟频域分辨率\\
增大采样时长 $T_{\rm p}$ 可改善模拟频率分辨率

\paragraph{截断与频谱泄露}
对一个无限长或非常长的信号通常需要在时域截断后再进行DFT处理\\
这相当于时域乘以矩形窗，频域与矩形窗频域进行卷积（造成频谱泄露）

\section{快速傅立叶变换}
\subsubsection{DFT运算特点}
要计算 $N$ 个频域点中的一点的值，需要的运算量：
\begin{enum}
    \item $N$次复数乘法，相当于 $4N$ 次实数乘法
    \item $N-1$ 次复数加法，相当于 $2(N-1)$ 次实数加法
\end{enum}

要得到DFT完整的$N$点频谱，上式需再乘以 $N$，因此：\\
DFT计算中的乘法、加法计算量均与 $N^2$ 成正比

利用系数 $W_{\rm N}^{nk}$ 的周期性、对称性，使DFT中的$N$ 项分组，可分解为更少点数的DFT\\
通过把长度为 $N$ 点的大点数DFT运算分解为多次小点数DFT运算来降低运算量

\subsection{按时间抽取的FFT}
假定点数 $N$ 是2的幂次，就可以将序列 $x(n)$ 按照序号奇偶分为两组
\begin{align*}
X(k) 
&= \sum_{r=0}^{N/2-1} x(2r) W_{N}^{2rk} + \sum_{r=0}^{N/2-1} x(2r+1) W_{N}^{(2r+1)k}   \\
&= \sum_{r=0}^{N/2-1} x(2r) W_{N}^{2rk} + W_N^k\sum_{r=0}^{N/2-1} x(2r+1) W_{N}^{2rk}  \\
&= \sum_{r=0}^{N/2-1} x_1(r) W_{N/2}^{rk} + W_N^k\sum_{r=0}^{N/2-1} x_2(r) W_{N/2}^{rk}  \\
&= X_1(k) + W_N^k X_2(k)
\end{align*}

虽然 $X_1(k), X_2(k)$ 只有 $N/2$ 个点，但可利用其周期性延拓为 $N$ 点
\begin{align*}
    &X_1(k+N/2) = X_1(k) &
    &X_2(k+N/2) = X_2(k)
\end{align*}

$$
X(k) = \left\{
\begin{aligned}
    &X_1(k) + W_N^k X_2(k), & k = 0, \cdots, \frac{N}{2}-1 \\
    &X_1(k) - W_N^k X_2(k), & k = \frac{N}{2} ,\cdots, N-1
\end{aligned}
\right.
$$

时间抽取法所需运算量与 $N\log_2N$ 成正比

\section{数字滤波器的结构}
